//! ## 26. Remove Duplicates from Sorted Array (easy, array, 双指针)
//! Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.
//!
//! Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
//!
//! #### Example 1
//! ```txt
//! Input: nums = [0,0,1,1,1,2,2,3,3,4]
//! Output: 5, nums = [0,1,2,3,4]
//! Explanation: Your function should return length = 5
//! ```
//! #### Constraints
//! - `0 <= nums.length <= 3 * 10e4`
//! - `-10e4 <= nums[i] <= 10e4`
//! - `num` is sorted in ascending order.
//!
//! ### 知识点
//! - 双指针问题
//!

pub struct Solution;

impl Solution {
    /// #### 思路
    /// 因为数组是排序的, 可以利用双指针 last, cur 进行比较,
    /// #### 算法
    /// last = 0;
    /// for cur in 1..n {...}
    /// 当 *cur == *last 时 cur++;
    /// 当 *cur != *last 时 last++; arr[last] = cur; cur++;
    /// #### 边界分析
    /// 当数组为空直接返回 0
    /// #### 复杂度
    /// - 时间复杂度 O(n)
    ///     - 只循环一遍数组
    /// - 空间复杂度 O(1)
    ///     - 不需要额外的存储空间
    pub fn solve(arr: &mut Vec<i32>) -> usize {
        if arr.is_empty() {
            return 0;
        }
        let mut last = 0;
        for cur in 1..arr.len() {
            if arr[cur] != arr[last] {
                last += 1;
                arr[last] = arr[cur];
            }
        }
        // 将多余的 pop
        while arr.len() > (last + 1) {
            arr.pop();
        }
        last + 1
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        let mut nums = vec![1, 1, 2];
        assert_eq!(Solution::solve(&mut nums), 2);
        assert_eq!(nums, vec![1, 2]);
        let mut nums = vec![0, 0, 1, 1, 1, 2, 2, 3, 3, 4];
        assert_eq!(Solution::solve(&mut nums), 5);
        assert_eq!(nums, vec![0, 1, 2, 3, 4]);
    }
}
